package com.lsa.helpers.graph;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

import com.lsa.helpers.Pair;

/**
 * Adjacency list graph
 * 
 * @author lsa
 *
 * @param <T> node attribute type
 * @param <U> edge attribute
 */
public class AdjGraph<T, U> implements IGraph<T, U>{
    private int nodeCount;
    private int edgeCount;
    private List<List<Integer>> adjacencyList;
    private List<T> nodeAttrs;
    private Map<Pair<Integer, Integer>, U> edge2Attr;
    private T defaultNodeAttr;
    private U defaultEdgeAttr;
    private boolean isDirected;
    
    public AdjGraph(boolean isDirected, int vertexCount) {
        this(isDirected, vertexCount, null);
    }
    
    public AdjGraph(boolean isDirected, int vertexCount, T defaultNodeAttr) {
        this(isDirected, vertexCount, defaultNodeAttr, null);
    }

    public AdjGraph(boolean isDirected, int nodeCount, T defaultNodeAttr, U defaultEdgeAttr) {
        this.isDirected = isDirected;
        this.nodeCount = nodeCount;
        this.edge2Attr = new LinkedHashMap<Pair<Integer,Integer>, U>();
        this.defaultNodeAttr = defaultNodeAttr;
        this.defaultEdgeAttr = defaultEdgeAttr;
        adjacencyList = new ArrayList<List<Integer>>(nodeCount);
        nodeAttrs = new ArrayList<T>();
        for (int i = 0; i < nodeCount; i++) {
            adjacencyList.add(new ArrayList<Integer>());
            nodeAttrs.add(defaultNodeAttr);
        }
    }
    
    @Override
    public int nodeCount() {
        return nodeCount;
    }
    
    @Override
    public int edgeCount() {
        return edgeCount;
    }
    
    @Override
    public boolean isDirected() {
        return isDirected;
    }
    
    public void init() {
        for (int i = 0; i < nodeCount; i++) {
            nodeAttrs.set(i, defaultNodeAttr);
        }
        edge2Attr.clear();
    }
    
    @Override
    public T nodeAttr(int u) {
        return nodeAttrs.get(u);
    }
    
    
    public U edgeAttr(int u, int v) {
        return edge2Attr.get(Pair.create(u, v));
    }
    
    @Override
    public int addNode(T data) {
        nodeCount++;
        adjacencyList.add(new ArrayList<Integer>());
        nodeAttrs.add(data);
        return nodeCount-1;
    }
    
    public void setNodeAttr(int u, T d) {
        nodeAttrs.set(u, d);
    }
    
    public List<Integer> adjacencyList(int u) {
        return adjacencyList.get(u);
    }
    
    public void addEdge(int u, int v) {
        addEdge(u, v, defaultEdgeAttr);
    }
    
    @Override
    public void addEdge(int u, int v, U edgeAttr) {
        ++edgeCount;
        List<Integer> list = adjacencyList.get(u);
        list.add(v);
        edge2Attr.put(Pair.create(u, v), edgeAttr);
        if (!isDirected) {
            addEdge(v, u, edgeAttr);
        }
    }
    
    @Override
    public boolean hasEdge(int from, int to) {
        return edge2Attr.containsKey(Pair.create(from, to));
    }
    
    public void setEdgeAttr(int u, int v, U edgeAttr) {
        edge2Attr.put(Pair.create(u, v), edgeAttr);
    }
   
    
    @Override
    public Iterator<T> vertexIterator() {
        return Collections.unmodifiableCollection(nodeAttrs).iterator();
    }
    
    @Override
    public Iterator<IEdgeNode<U>> edgeIterator() {
        final Iterator<Entry<Pair<Integer, Integer>, U>> iter = edge2Attr.entrySet().iterator();
        return new Iterator<IEdgeNode<U>>(){

            @Override
            public boolean hasNext() {
                return iter.hasNext();
            }

            @Override
            public IEdgeNode<U> next() {
                final Entry<Pair<Integer, Integer>, U> entry = iter.next();
                final Pair<Integer, Integer> edge = entry.getKey();
                return new EdgeNode<U>(edge.getFirst(), edge.getSecond(), entry.getValue());
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
}